package question6_10;

/**
 * @description: 斐波那契数列
 * @author: jhy
 * @time: 2021/5/19 19:52
 */
public class Question10 {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        Question10 question10 = new Question10();
        question10.fibonacci2(39);
        long end = System.currentTimeMillis();
        System.out.println("耗时"+ (end - start));
    }


    //递归 --->会导致大量重复计算
    public int fibonacci(int n) {
        if(n == 0 || n == 1){
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    //优化递归--->保存中间结果
    public int fibonacci2(int n) {
        if(n == 0 || n == 1){
            return n;
        }
        int[] ints = new int[n + 1];
        ints[0] = 0;
        ints[1] = 1;
        for(int i = 2;i < n + 1;i++){
            ints[i] = ints[i-1] + ints[i-2];
        }
        return ints[n];
    }
}
